The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for accelerating arithmetic decoding, such as in context-based adaptive binary arithmetic coding (CABAC).
In today's society, data networks are increasingly used as a source of multimedia content that is downloaded or streamed from server computing devices to client computing devices, provided over wireless communications to portable computing devices, across fiber optic connections to television receivers, and the like. The ever increasing demand for multimedia content over data networks has greatly outpaced the increases in bandwidth of the data communication connections over which this multimedia content is provided. Thus, it becomes increasingly more important for ways to be devised to reduce the size of the multimedia content.
One way of reducing the size of this multimedia content is to use entropy encoding mechanisms, such as Huffman coding, arithmetic coding, adaptive arithmetic coding, and the like. Entropy encoding is a coding scheme that involves assigning codes to symbols in the multimedia content so as to match code lengths with the probabilities of the symbols. Typically, entropy encoders are used to compress data by replacing symbols, represented by equal length code segments, with symbols represented by codes proportional to the negative logarithm of the probability. As a result, the most common symbols use the shortest codes. Huffman coding is one type of entropy encoding in which an alphabet is mapped to a representation of that alphabet composed of strings of variable size so that symbols that have a higher probability of occurring have a smaller representation than those that occur less often. An arithmetic encoder takes a string of symbols as input and produces a rational number in the interval [0, 1] as output. Adaptive arithmetic encoders/decoders generally consume a stream and decode symbols using one or more probability estimates for the probability of the next symbol with the probability being adjusted according to the actual symbol decoded.
Various standards have been developed to improve the visual quality of multimedia content while providing overall smaller data size multimedia files. One of these standards, the H.264 specification (also known as the ISO Motion Picture Experts Group (MPEG)-4 part 10), is a high compression digital video codec standard. An H.264 compliant codec can encode video with approximately three times fewer bits than comparable MPEG-2 encoders while retaining similar video quality. The H.264 specification provides for two types of entropy encoding processes, including context-adaptive binary arithmetic coding (CABAC) and context-adaptive variable length coding (CAVLC). With regard to CABAC, the CABAC coder has multiple probability modes for different contexts, where a “context” is a probability model for the multimedia content that is dynamically updated and contains the probability that a particular symbol is likely to occur based on the number of previous instances of the symbol in the multimedia content. The CABAC coder first converts all non-binary symbols to binary and then, for each bit, the CABAC coder selects which probability model to use. The CABAC coder then uses information from nearby elements to optimize the probability estimate. Arithmetic coding is then applied to compress the data. More information regarding CABAC and CAVLC may be found in Marpe et al., “Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, July 1303, pages 620-636.
CABAC decoding operations are typically sequential in nature, requiring extensive computations to calculate various parameters including range, offset, and context information. Currently, CABAC decoding is either done by software running on a central processing unit, a dedicated special purpose processor, or specially designed CABAC decoder hardware unit which sends the resulting symbol stream either to a processor or to another hardware unit concerned with the next step of the H.264 decoding operation. The operation count suffered by central processing unit, the dedicated special purpose processor, or CABAC decoder is fairly costly and does not take advantage of any parallelism that may be achievable in the CABAC decoding process. Thus, CABAC decoding tends to be a source of inefficiency in the processing of multimedia content due to the extra overhead of processor cycles, consumed resources, and the like, required to perform the CABAC decoding.